CF906C Party

首先预处理出一个人能介绍的人的集合 relrel 。(包括他本身)

dp(S)dp(S) 表示让集合 SS 中的人相互认识最少需要几个人。

那么可以刷表转移:

dp(Sreli)=min(dp(S)+1)      (iS)dp(S | rel_i )=\min(dp(S)+1)~~~~~~ (i\in S)

边界条件 dp(reli)=1dp(rel_i)=1

可以看出,第一问的答案为全集的 dp 值。

第二问记录前驱状态和转移到当前状态用的人即可。

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

const int MAXN = 22;
int n , m , rel[ MAXN + 5 ];
int dp[ 1 << MAXN ] , pre[ 1 << MAXN ] , prei[ 1 << MAXN ];

int main( ) {
	scanf("%d %d",&n,&m);
	if( m == n * ( n - 1 ) / 2 ) return printf("0") & 0;
	for( int i = 1 , u , v ; i <= m ; i ++ ) {
		scanf("%d %d",&u,&v); u -- , v --;
		rel[ u ] |= 1 << v; rel[ v ] |= 1 << u;
	}
	for( int i = 0 ; i < n ; i ++ ) rel[ i ] |= 1 << i;
	
	memset( dp , 0x3f , sizeof( dp ) );
	for( int i = 0 ; i < n ; i ++ ) dp[ rel[ i ] ] = 1 , prei[ rel[ i ] ] = i;
	for( int S = 0 ; S < 1 << n ; S ++ )
		for( int i = 0 ; i < n ; i ++ )
			if( S & ( 1 << i ) && dp[ S | rel[ i ] ] > dp[ S ] + 1 ) {
				dp[ S | rel[ i ] ] = dp[ S ] + 1;
				pre[ S | rel[ i ] ] = S; prei[ S | rel[ i ] ] = i;
			}
	printf("%d\n", dp[ ( 1 << n ) - 1 ] );
	for( int i = ( 1 << n ) - 1 ; i ; i = pre[ i ] ) printf("%d " , prei[ i ] + 1 );
	return 0;
}